package basis.netease.medium;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 7-16 删除有序链表中重复2次以上元素
 * 给出一个升序排序的链表 L，删除链表中重复2次以上出现的元素，只保留原链表中出现一次或重复2次 的元素。
 * 例如：
 * 给出的链表为 1→2→3→3→4→4→4→4→5, 返回 1→2→3→3→5.
 * 给出的链表为1→1→1→2→3, 返回 2→3.
 * 数据范围： 链表长度 0≤size≤100000，链表中的值满足 ∣val∣≤10000。
 * 输入格式:
 * 第一行包含头节点地址，总节点数量 N （1≤N≤100000）
 * 节点地址用一个 5 位非负整数表示（可能有前导 0），NULL 用 −1 表示。
 * 接下来 N 行，每行描述一个节点的信息，格式如下：
 * Address Data Next
 * 其中 Address 是节点地址，Data 是一个绝对值不超过100000的整数，Next 是下一个节点的地址。
 * 输出格式:
 * 输出删除有序链表中重复2次以上元素后的链表。每个结点占一行，按输入的格式输出。
 * 输入样例:
 * 在这里给出一组输入。例如：
 * 00100 10
 * 99999 3 87654
 * 87654 4 11111
 * 55555 8 -1
 * 44444 4 55555
 * 23854 2 00000
 * 11111 4 22222
 * 00100 1 23854
 * 22222 4 33333
 * 00000 3 99999
 * 33333 4 44444
 * 输出样例:
 * 在这里给出相应的输出。例如：
 * 00100 1 23854
 * 23854 2 00000
 * 00000 3 99999
 * 99999 3 55555
 * 55555 8 -1
 */
public class Main_13 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] params = in.nextLine().split(" ");
        String rootAddress = params[0];
        int n = Integer.parseInt(params[1]);
        Map<String, Node> nodeMap = new HashMap<>();
        Map<String, Integer> countMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String[] lineArr = in.nextLine().split(" ");
            nodeMap.put(lineArr[0], new Node(lineArr[0], lineArr[1], lineArr[2]));
            Integer count = countMap.get(lineArr[1]);
            if (count != null) {
                countMap.put(lineArr[1], count + 1);
            } else {
                countMap.put(lineArr[1], 1);
            }
        }
        Node node = removeNode(nodeMap, countMap, rootAddress);
        while (node != null) {
            System.out.println(node);
            node = nodeMap.get(node.next);
        }
    }

    public static Node removeNode(Map<String, Node> nodeMap, Map<String, Integer> countMap, String rootAddress) {
        // 当前遍历到的节点
        Node currentNode = nodeMap.get(rootAddress);
        // 当前遍历到的节点的上一个节点（如果currentNode需要删除，则把currentNode的lastNode.next更新为currentNode.next.address）
        Node lastNode = null;
        // 需要返回的最终跟节点
        Node root = currentNode;
        while (currentNode != null) {
            String nextAddress = currentNode.next;
            Integer count = countMap.get(currentNode.data);
            if (count > 2) {
                Node nextNode = nodeMap.get(nextAddress);
                currentNode = nextNode;
                if (lastNode == null) {
                    // 不存在上个节点，表示当前遍历到的节点为根节点
                    root = currentNode;
                    continue;
                }
                lastNode.next = nextAddress;
            } else {
                lastNode = currentNode;
                currentNode = nodeMap.get(nextAddress);
            }
        }
        return root;
    }

    static class Node {
        String address;
        String data;
        String next;

        Node(String address, String data, String next) {
            this.address = address;
            this.data = data;
            this.next = next;
        }

        public String toString() {
            return address + " " + data + " " + next;
        }
    }

}
